package java_0306_MapAndSet.leetcode;

/**
 * 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
 * 构造这个链表的深拷贝。深拷贝应该正好由n个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。
 * 新节点的next指针和random指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。
 * 复制链表中的指针都不应指向原链表中的节点
 */
//注意：在做数据结构和算法题是，不要看是链表题就只想着链表，注意换思路
//Map接口=》映射：Map<K,V>:一个k对应一个v,新链表和原链表除了地址不同，其余对应关系完全相同，原1=>新1；原2=>新2

import java.util.HashMap;
import java.util.Map;

/**
 * 分析：
 * 1.先不管random，就进行普通链表的深拷贝：边遍历原链表，每当走到一个原链表的节点就创建一个新节点，值与原链表相同
 * 链表链接：next的连接：创建一个虚拟头节点，进行尾插法，就可以连接新链表的next域
 * 2.random的连接：很难进行操作：换思路
 * //注意：在做数据结构和算法题是，不要看是链表题就只想着链表，注意换思路
 * //Map接口=》映射：Map<K,V>:一个k对应一个v,新链表和原链表除了地址不同，其余对应关系完全相同，原1=>新1；原2=>新2
 * 新链表的next和random都可以从原链表中一一映射过来
 * 思路：
 * Map集合键值对对应旧链表的节点与新链表的节点（一个旧链表节点肯定对应一个新链表节点）
 */
public class Num138_CopyRandomList {
    private class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head) {
        //边界
        if(head==null){
            return null;
        }
        //遍历原链表，构造新链表的节点，存储在Map的val中
        Map<Node,Node> nodeMap=new HashMap<>();
        for(Node x=head;x!=null;x=x.next){
            //构造原链表的节点
            Node node=new Node(x.val);
            nodeMap.put(x,node);
        }
        //对新链表进行连接操作
        //原1和新1next,random一一对应（新1.next=新3：新地址是根据原3取得）
        for(Node x=head;x!=null;x=x.next){
            //新链表的random和next和原链表一一对应
            //对于Map来说，key值都是原链表的节点
            //原1.next=原3
            nodeMap.get(x).next=nodeMap.get(x.next);//nodeMap.get(x)：获取到原1对应的新1；nodeMap.get(x.next):根据原链表下一个节点获取新链表的下一个节点
            //原1.random=原5
            nodeMap.get(x).random=nodeMap.get(x.random);
        }
        //返回新链表的头节点：就是原链表头节点的映射
        return nodeMap.get(head);
    }
}
